package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution503 {
  public static int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ret = new int[n];
    Arrays.fill(ret, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n * 2 + 1; i++) {
      while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
        ret[stack.pop()] = nums[i % n];
      }
      stack.push(i % n);
    }
    return ret;
  }

  public static void main(String[] args) {
    Arrays.asList(nextGreaterElements(new int[]{2, 1, 4, 3})).stream().forEach(System.out::print);
  }
}